Learning

Chapter 15 Database System Concepts

15.1 基于锁的协议

确保隔离性的方法之一是要求对数据项以互斥的方式进行访问。实现该需求的最常用的方法是只允许事务访问当前该事务持有锁的数据项。

15.1.1 锁

共享型锁和排他型锁

过早释放数据项可能会导致别的事务看到一个不一致的状态。还可能会导致事务的死锁和饿死状态。

我们如果不使用封锁，或者我们对数据项进行读写之后立即解锁，那么我们可能会进入不一致的状态。另一方面，如果在申请对另一数据项加锁之前如果我们不对当前锁住的数据项解锁，则可能会发生死锁。如果采用封锁，那么死锁是肯定会发生的，但总比发生不一致要好。因为可以通过回滚事务来解决死锁问题。

两个事务$T_i$和$T_j$对于一个事务持有不相容的锁。如果有不相容的锁，并且在调度中$T_i$会先持有锁，那么说$T_i$先于$T_j$，同时拥有一个从$T_i$到$T_j$的箭头。跟优先图类似，如果存在环的话，就说明这个调度不是合法的。

15.1.2 锁的授予

按照如下方式来授权锁可以避免事务饿死，当事务$T_i$对数据项Q加M型锁时，并发控制管理器授权加锁的条件：

  • 不存在在数据项Q上持有与M型锁冲突的锁的其他事务
  • 不存在等待对数据项Q加锁且先于$T_i$申请加锁的事务。

15.1.3 两阶段封锁协议

该协议要求每个事务分两个阶段提出加锁和解锁申请。

  • 增长阶段：事务可以获得锁，但不能释放锁
  • 缩减阶段：事务可以释放锁，但是不能获得新锁

一个事务获得其最后加锁的位置（增长阶段结束点）称为事务的封锁点。多个事务可以根据它们的封锁点进行排序，实际上，这个顺序就是事务的一个可串行化顺序。

这个协议并不保证不会发生死锁。同时也不保证时无级联的。

级联回滚可以通过讲两阶段封锁修改为严格两阶段封锁协议加以避免。这个协议要求在两阶段封锁协议的基础上限制所有的排他锁的释放都必须在事务提交之后才能释放。这样可以让别的事务在他还没提交的时候是无法读取到他写的值。避免了级联回滚。

另一个两阶段封锁的变体是强两阶段封锁协议，它要求事务提交之前不的释放任何锁，连共享锁都不释放了。

为了更好的并发性，允许锁的转换，从共享锁到排他锁称为升级，反之则称为降级。升级只能发生在增长阶段，降级只能发生在缩减阶段。

严格两阶段封锁与强两阶段封锁包含锁转换，在商用数据库系统中广泛使用。

这里介绍一种自动加锁、解锁的指令

  • 当事务$T_i$进行read(Q)的操作时，系统就产生一条lock-S(Q)指令，该read(Q)指令紧跟其后。
  • 事务$T_i$进行write(Q)操作时，系统检查$T_i$是否已在Q上持有共享锁。若有，则系统发出upgrade(Q)指令，后接write(Q)指令。否则系统发出lock-X(Q)指令，后接write(Q)指令。
  • 当一个事务提交或中止后，该事务持有的所有锁都被释放。

15.1.4 封锁的实现

锁管理器可以实现为一个过程，它从事务接受消息并反馈信息。锁管理器过程针对锁请求消息返回授予锁信息，或者要求事务回滚的消息（发生死锁时）。

锁管理器为目前已加锁的每个数据项维护一个链表，每一个请求为链表中的一个记录，按请求到达的顺序排序。它使用一个以数据项名称为索引的散列表来查找链表中的数据项。这个表叫做锁表。锁表采用的溢出链。

处理过程

  • 当一条锁请求消息到达时，如果相应数据项的链表存在，在该链表末尾增加一个记录；否则新建一个仅包含该请求记录的链表。在当前没有加锁的数据项上总是授予第一次加锁请求，但当事务向已被加锁的数据项加锁时，只有当该请求与当前持有的锁相容，并且所有先前的请求都已授予锁的条件下，锁管理器才为该请求授予锁，否则该请求只好等待。

  • 当锁管理器收到一个事务的解锁信息时，它将与该事务相对应的数据项链表中的记录删除，然后检查随后的记录，如果有，如前所述，就看该请求能否被授权，如果能，锁管理器授权该请求并处理其后记录，如果还有，类似地一个接一个地处理。

  • 如果一个事务中止，锁管理器删除该事务产生的正在等待加锁的所有请求。一旦数据库系统采取适当动作撤销该事务，该中止事务持有的所有锁将被释放。

这个算法保证了锁请求无饿死现象，因为在先前接收到的请求正在等待加锁时，后来者不可能获得授权。

15.1.5 基于图的协议

如果要开发非两阶段协议，我们需要有关每个事务如何存取数据库的附加信息。最简单的模型要求我们事先知道访问数据项的顺序。

为了获取这些事先的知识，我们要求所有数据项集合$D={d_1,d_2,...,d_n}$满足偏序$\rightarrow$：如果$d_i \rightarrow d_j$，则任何既访问$d_i$又访问$d_j$的事务必须首先访问$d_i$然后再访问$d_j$。这种偏序可以是数据的逻辑或物理组织的结果，也可以只是为了并发控制而加上的。

偏序意味着会是个无环图，称为数据库图。

给出一个称为树形协议的简单协议，该协议只使用排他锁。在树形应协议中，可用的加锁指令只有lock-X。每个事务$T_i$对一数据项最多能加一次锁，并且遵从以下规则：

  • $T_i$首次加锁可以对任何数据进行
  • 此后，$T_i$对数据项Q加锁的前提是$T_i$当前持有Q的父项上的锁
  • 对数据项解锁可以随时进行
  • 数据项$T_i$加锁并解锁后，$T_i$不能再对数据项加锁。

所有满足树形协议的调度是冲突可串行化的。并且保证不会产生死锁。但是不保证可恢复性和无级联回滚。为了保证可恢复性和无级联回滚，将协议修改为在事务结束前不允许释放排他锁。但是这就降低了并发度，有一个替代方案，但只保证了可恢复性：为每一个发生了提交写操作的数据项，我们记录是哪个事务最后对它执行了写操作，当事务$T_i$执行了对未提交数据项的读操作，我们就在最后对该数据项执行了写操作的事务上记录一个$T_i$的提交依赖，在有$T_i$的提交依赖的所有事务提交完成之前，$T_i$不得提交。如果其中任何一个事务中止，$T_i$也必须中止。

树形协议不产生死锁，所以不需要回滚。树形封锁协议的另一个优点是可以在较早时候释放锁，但是它封锁了一些额外的数据，会对并发性造成影响。

15.2 死锁处理

死锁处理主要有两种方式

  • 死锁预防，不让系统出现任何死锁的状况
  • 死锁的检测和恢复

两种方法都会导致事务的回滚。

15.2.1 死锁预防

一种方式是通过对加锁请求进行排序或要求同时获得所有的锁来保证不会发生循环等待。另一种方法比较接近死锁恢复，每当等待有可能导致死锁，进行事务回滚而不是等待加锁。

防止死锁的第一种方法是要求事务在开始之前就把所有需要使用到的数据项加上锁。另一个机制是对所有的数据项加上一个次序，同时要求事务只能按次序规定的顺序封锁数据项。比如使用全序关系，一旦一个事务锁住了某个特定的数据项，它就不能申请顺序中位于该数据项前面的数据项上的锁了。

第二种方法就是使用抢占和事务回滚。系统通过时间戳来判断是否允许强占。若一个事务回滚，则使用它原先的时间戳。

已提出的利用时间戳的两种不同的死锁预防机制。

  • wait-die机制基于非强占。当一个事务$T_i$想要获得的锁被比他新的事务所占据的时候，允许$T_i$等待，否则就让它自己滚（回滚）！

  • wound-wait机制是基于抢占的技术。当事务$T_i$申请的数据项被$T_j$持有，仅当$T_i$比$T_j$年轻，允许$T_i$等待，否则就让$T_j$滚。

这两种机制都需要面临不必要的回滚。

还有一个基于锁超时的方法。但是超时的阈值难以判断，因此使用不多。

15.2.2 死锁检测与恢复

系统想要破解一个死锁的状况的话，系统必须

  • 维护当前数据项分配给事务的有关信息，以及任何尚未解决的数据项请求信息
  • 提供一个使用这些信息判断系统是否进入死锁状态的算法
  • 当检测算法判定存在死锁时，从死锁中恢复

15.2.2.1 死锁检测

死锁可以用称为等待图的有向图来精确描述。$T_i \rightarrow T_j$表示事务$T_i$在等待$T_j$释放所需要的数据项。这个图是动态变化的。一旦出现环，说明存在死锁，环上的所有事务都是处在死锁的状态下。

15.2.2.2 从死锁中恢复

解除死锁最通常的做法是回滚一个或多个事务。

需要解决三个问题

  • 一个是选择谁来回滚，通常是选择系统认为代价小的事务来回滚
  • 回滚的距离，是彻底回滚还是部分回滚
  • 要避免有些事务不断被回滚而饿死。

15.3 多粒度

通过允许各种大小的数据项并定义数据粒度的层次结构，其中小粒度数据项嵌套在大粒度数据项中来实现。当事务对一个结点加锁，或为共享锁或为排他锁，该事务也以同样类型的锁隐式地封锁这个结点的全部后代结点。加锁的时候要延路径查看，当路径上所有结点的锁有一个出现互斥的话，就无法加锁。

意向锁来解决当要大粒度封锁的时候，检查小粒度是否上锁了。如果一个结点加了意向锁，则说明它在树的较低层次进行显示加锁了。在一个结点显示加锁之前，要对它的所有祖先结点加上意向锁。共享型意向锁(IS)、排他型意向锁（IX）。若一个结点加上了共享排他型意向锁(SIX)，则说明以该结点为根的子树显式地加了共享锁，并且在树的更低层显示地加了排他锁。

15.4 基于时间戳的协议

前面所说的所有的封锁协议中，每一对冲突事务的次序是在执行时由二者都申请的，但类型不相容的第一个锁决定的。另一种决定事务可串行化次序的方法是事先选定事务的次序。其中最常用的方法就是时间戳排序机制。

15.4.1 时间戳

对于一个事务$T_i$，把唯一一个时间戳$TS(T_i)$和它联系起来。

时间戳可以是系统时钟或逻辑计数器，其中逻辑计数器在每赋予一个时间戳之后自加1。

还需要两个时间戳：

  • W-timestamp(Q)表示成功执行write(Q)的所有事务的最大时间戳
  • R-timestamp(Q)表示成功执行read(Q)的所有事务的最大时间戳

15.4.2 时间戳排序协议

  • 假设事务$T_i$发出read(Q)。
    • 若$TS(T_i) \gt W-timestamp(Q)$，则说明$TS(T_i)$需要读入的Q值已被覆盖。因此read操作被拒绝，$TS(T_i)$回滚
    • 若$TS(T_i) \leq W-timestamp(Q)$
  • 假设事务发出了write(Q)：
    • 若$TS(T_i) \le R-timestamp(Q)$，则$T_i(Q)$产生的Q值是先前所需要的，且系统已经假定该值不会再产生。因此write被拒绝，并且事务被回滚
    • 若$TS(T_i) \le W-timestamp(Q)$，则$T_i$试图写入的Q值已过时。因此，write操作被拒绝，事务回滚
    • 其他情况下，系统执行write操作，将W-timestamp(Q)设置为$TS(T_i)$

被回滚的事务都会有一个新的时间戳。该协议保证无死锁，因为不存在等待的事务。但是有可能会饿死。该协议还会产生不可恢复的调度，但可以用下面的任何一个方法来保证可恢复性。

  • 在事务末尾执行所有的写操作，并且在写的时候不允许访问已写完的任何数据项
  • 可恢复性和无级联性也可通过使用一个受限的封锁形式来保证，由此，对未提交数据项的读操作被推迟到更新该数据项的事务提交之后
  • 可恢复性可以通过跟踪未提交写操作来单独保证。一个事务读取了别的事务所写的数据后，只能等别的事务也提交了之后他才能提交。

15.4.3 Thomas写规则

这里提供一个例子

$T_{27}$ $T_{28}$
read(Q)
write(Q)
write(Q)

当$T_{27}$执行write(Q)是，发现已经被$T_{28}$写了，就会被回滚。但这是不必要的。

可以修改一下时间戳协议，其中关于读的不变，对于写的部分做了修改。对于其中的第二条

  • 若$TS(T_i) \le W-timestamp(Q)$，则$T_i$试图写入的Q值已过时。因此，write操作被拒绝，事务回滚

修改为

  • 若$TS(T_i) \le W-timestamp(Q)$，则$T_i$试图写入的Q值已过时。则将write忽略。

这样就避免了回滚。当然也要首先检查第一条规则。

他产生视图可串行化调度。

视图可串行化

每个冲突可串行化调度都是视图可串行化调度，但存在非冲突可串行化的视图可串行化调度。

基于有效性检查的协议

要求每个事务$T_i$在其生命周期中按两个或三个阶段执行，这取决于该事务是一个只读事务还是一个更新事务。

  1. 读阶段：在这一阶段中，系统执行事务$T_i$。各数据项值被读入并保存在事务$T_i$的局部变量中。所有write操作都是对局部临时变量进行的，并不对数据库进行真正的更新。
  2. 有效性检查阶段：对事务$T_i$进行有效性测试。判定是否可以执行write操作而不违反可串行性。如果事务有效性测试失败，则系统终止这个事务。
  3. 写阶段：若事务$T_i$已通过有效性检查，则保存$T_i$任何写操作结果的临时局部变量值都被复制到数据库中。

只读事务只有前面两个阶段。

给事务定义另外三个时间

  1. Start($T_i$)
  2. Validation($T_i$)
  3. Stop($T_i$)

其中将Validation($T_i$)作为事务本省的时间戳TS($T_i$)。并利用时间戳排序技术决定可串行性顺序。选择Validation($T_i$)来作为TS，是我因为在冲突频率很低的读阶段可以获得更快的响应时间。

有效性测试：对于任何满足TS($T_k$) < TS($T_i$)的事务TS($T_k$)必须满足下面条件之一：

  1. Finish($T_k$) < Start($T_i$)
  2. $T_k$所写的数据项集与$T_i$所读数据项集不相交。并且$T_k$的写阶段在$T_i$开始有效性检查之前就开始了。即$Start(T_i) \le Finish(T_k) \le Validation(T_i)$。这个条件保证了二者写不重叠。

15.6 多版本机制

前面的并发控制机制要么延迟一项操作要么中止发出该操作的事务来保证可串行性。在多版本并发控制机制中，每个write(Q)操作创建Q的一个新版本。当事务发出一个read(Q)操作时，并发控制管理器选择Q的一个版本进行读取。并发控制机制必须保证用于读取的版本的选择能保持可串行性。

15.6.1 多版本时间戳排序

对于每个数据项Q，有一个版本序列$Q_1,Q_2,Q_3,...,Q_k$。每个版本都包含三个数据字段：

  • Content(Q)
  • W-timestamp(Q)
  • R-timestamp(Q)
    如果事务通过发出write(Q)操作创建了一个Q的新版本，那么它的两个读写时间都用事务的时间戳来初始化。

事务读取离现在最近的一个版本
当事务发出写请求的时候，如果事务时间戳小于W-timestamp(Q)的话，则事务回滚，若等于则覆盖，若大于则创建新的版本。（针对最近的一个版本的时间戳）

除此之外还多了一个需要删除无用的版本。当$Q_k$和$Q_j$的时间戳都小于系统中最老的事务的时间戳，则其中的较老的一个需要删除。

读请求从不失败且不需要等待。但是读请求需要写时间戳，产生磁盘操作。

通过扩展来获得可恢复性和无级联性。

15.6.2 多版本两阶段锁

该协议对只读事务和更新事务加以区分。

更新事务执行两阶段封锁协议；即它们持有全部锁到事务结束。因此它们可以按提交顺序进行串行化。用计数器作为时间戳。

只读事务在执行读操作时遵从多版本时间戳协议。

当更新事务读取一个数据项时，它在获得该数据项上的共享锁后读取该数据项最新版本的值。当更新事务想写一个数据项时，它首先要获得该数据项上的排他锁，然后为此数据项创建一个新版本。新版本的时间戳初始化为无穷大。当更新事务完成后，再设置成计数器加1的值。这个协议保证了调度是可恢复的和无级联的。版本删除同多版本时间戳协议一样。

15.7快照隔离

这种隔离对于只读事务来说是理想的，因为它们不用等待，也不会被并发管理器中止。

15.7.1 更新事务的有效性检验步骤

先提交者获胜

检查是否有与$T$并发执行的事务，对于$T$打算写入的某些数据，该事务已经将更新写入数据库。

如果发现这样的事务，则$T$中止。

如果没有发现这样的事务，则$T$提交，并且将更新写入数据库。

先更新者获胜

当事务$T_i$试图更新一个数据项时，它请求该数据项的一个写锁，拿到锁之后它需要检查是否被并发事务更新过，如果发现被写过则需要中止。

快照隔离并不保证调度时可串行的

比如同时创建订单，两个任务在创建订单的时候看到的都是相同的已有的订单集合，但订单的编号时逐个加1的话，就会出现订单号相同的情况了。

插入操作、删除操作与谓词读

分享到